﻿#define _CRT_SECURE_NO_WARNINGS
#include"Graph.h"
 
//全局变量标志数组
bool visited[MVNum] = { false };

//邻接矩阵的创建
void CreateUDN(AMGraph* G)
{
	assert(G);
	//输入总顶点数，输入总边数
	printf("输入总顶点数、总边数：");
	fscanf(stdin, "%d %d", &(G->vexnum), &(G->arcnum));
	while ((getchar() != '\n'))
	{
		;
	}

	int i = 0;
	int j = 0;
	printf("依次输入点的信息：");
	//依次输入点的信息
	for (i = 0; i < G->vexnum; i++)
		scanf(" %c", &(G->vexs[i]));//这里%c后有空格，输入最后一个数据时别忘了输入空格
	while ((getchar() != '\n'))
	{
		;
	}

	//初始化邻接矩阵，边的权值，均置为最大值
	for (i = 0; i < G->vexnum; i++)
		for (j = 0; j < G->vexnum; j++)
			G->arcs[i][j] = MaxInt;

	int k = 0;
	VerTexType v1, v2;			//两个点
	ArcType w;					//权值
	//构造邻接矩阵
	for (k = 0; k < G->arcnum; k++)
	{
		printf("输入一条边依附的顶点和权值：");
		//输入一条边依附的顶点和权值
		fscanf(stdin, "%c %c %d", &v1, &v2, &w);
		while ((getchar()) != '\n')
		{
			;
		}
		//确定v1和v2在图中的位置，即顶点数组的下标
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G->arcs[i][j] = w;
		G->arcs[j][i] = G->arcs[i][j];//无向图矩阵对称
	}
}

//查找顶点的位置
int LocateVex(AMGraph* G, VerTexType v)
{
	assert(G);
	int i = 0;
	for (i = 0; i < G->vexnum; i++)
	{
		if (G->vexs[i] == v)
		{
			return i;
		}
	}
	//找不到，程序异常退出
	printf("找不到\n");
	exit(0);
}

//打印邻接矩阵
void PrintArcs(AMGraph* G)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < G->vexnum; i++)
	{
		for (j = 0; j < G->vexnum; j++)
			printf("%-5d ", G->arcs[i][j]);
		printf("\n");
	}
}


//Prim算法
//	1.首先，将初始顶点u加入U中，对其余的每一个顶点vj，将closedge[j]均初始化到u的边信息
//	2.循环n-1次，做如下处理
//		a.从各组边closedge中选出最小边closedge[k]，输出此边
//		b.将k加入U中
//		c.更新剩余的每组最小边信息closedge[j]，对于V-U中的边，
//		  新增加了一条从k到j的边，如果新边的权值比closedge[j].lowcost小，
//		  则将closedge[j].lowcost更新为新边的权值

//无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，输出T的各条边
void MiniSpanTree_Prim(AMGraph* G, VerTexType u)
{
	int k = LocateVex(G, u);		//k为顶点u的下标

	//初始化closedge数组
	for (int j = 0; j < G->vexnum; j++)
	{
		if (j != k)					//去掉回路
		{
			closedge[j].adjvex = u;
			closedge[j].lowcost = G->arcs[k][j];
		}
	}

	//某个顶点对应的closedge数组权值为0时，就表示这个顶点并入U集合了
	closedge[k].lowcost = 0;		//初始化，U={u}
	
	//选择其余n-1个顶点，生成n-1条边(n = G->vexnum)
	for (int i = 1; i < G->vexnum; i++)//i从1开始
	{
		k = Min(G, closedge);						//从u的各临边中选出最小的边

		//求出最小生成树的下一个节点：第k个节点，closedge[k]中存有当前最小边
		VerTexType u0 = closedge[k].adjvex;		//u0是最小边中的一个顶点，u0属于U
		VerTexType v0 = G->vexs[k];				//v0为最小边的另一个顶点，v0属于V-U
		printf("%c-%c\n", u0, v0);				//输出当前最小边

		closedge[k].lowcost = 0;				//第k个顶点并入U集

		for (int j = 0; j < G->vexnum; j++)
		{
			if (G->arcs[k][j] < closedge[j].lowcost)
			{
				closedge[j].adjvex = G->vexs[k];
				closedge[j].lowcost = G->arcs[k][j];
			}
		}
	}
}

//查找closedge数组中的最小权值
int Min(AMGraph* G, struct Auxiliary* closedge)
{
	int i = 0;
	int min = MaxInt;
	for (i = 0; i < G->vexnum; i++)
	{
		if (closedge[i].lowcost < min && closedge[i].lowcost != 0)
			min = closedge[i].lowcost;
	}
	for (i = 0; i < G->vexnum; i++)
	{
		if (closedge[i].lowcost == min)
			return i;
	}
	exit(0);
}